Easy2Siksha.com
Note: GNDU has shuffled some subjects between semesters (e.g., C Programming from 1st Sem to 3rd Sem), but the
syllabus and most questions are still similar, so don’t get confused — you are studying from the correct papers.
GNDU Question Paper-2025
Bachelor of Computer Application (BCA) (Hons.)
DATA STRUCTURES & FILE PROCESSING
Time Allowed: Three Hours Max. Marks: 75
Note: Attempt Five questions in all, selecting at least One question from each section. The
Fifth question may be attempted from any section. All questions carry equal marks.
SECTION-A
1. Write a step-by-step explanation of how linear search works to find an element in an unsorted
list. Also write pseudo code to implement it and analyse its time complexity and space complexity.
2. Explain the concept of a Stack data structure. Discuss its main operations and show how a stack
can be implemented using arrays. Illustrate each operation with an example and analyse its time
complexity.
SECTION-B
3. What is linked list? How is it represented in the memory? Write an algorithm to insert a new
node at a given location in the linked list. Explain this process with the help of an example.
4. Explain how a priority queue works. Describe the insertion and deletion operations with the
help of an example. How is a priority queue different from a normal queue and where can it be
applied effectively?
SECTION-C
5. What do you mean by Binary Tree? How is it implemented in the memory? Explain different
ways to traverse a binary tree using suitable example.
Easy2Siksha.com
6. What is Graph? How is it represented in the memory? Explain Breadth-First Search method to
traverse a node of a Graph using suitable example.
SECTION-D
7. Explain the process of Bubble sort using suitable example. Write an algorithm that performs
Bubble sort. Also determine its complexity.
8. Explain in detail the various file organization techniques used in data structures. Discuss the
advantages, disadvantages, and applications of each technique such as sequential, direct, and
indexed file organization. Illustrate your answer with suitable examples.
Easy2Siksha.com
GNDU Answer Paper-2025
Bachelor of Computer Application (BCA) (Hons.)
DATA STRUCTURES & FILE PROCESSING
Time Allowed: Three Hours Max. Marks: 75
Note: Attempt Five questions in all, selecting at least One question from each section. The
Fifth question may be attempted from any section. All questions carry equal marks.
SECTION-A
1. Write a step-by-step explanation of how linear search works to find an element in an unsorted
list. Also write pseudo code to implement it and analyse its time complexity and space complexity.
Ans: Files are an important part of programming because they allow us to store data
permanently. Normally, when we run a Python program, the data is stored in the
computer's memory (RAM). Once the program ends, that data disappears. However, by
using files, we can save information so that it remains available even after the program is
closed.
Think of a file like a notebook. You can open the notebook, write something in it, close it,
and later open it again to read what you wrote. Python works with files in the same way.
What is File Processing?
File processing is the process of creating, opening, reading, writing, updating, and closing
files using a Python program.
For example:
• Saving student records
• Storing employee details
• Writing exam results
• Saving application logs
• Creating reports
Instead of entering data every time the program runs, Python stores it inside a file.
Easy2Siksha.com
Steps of File Processing in Python
Python follows a simple sequence while working with files.
Start
│
▼
Open the File
│
▼
Read or Write Data
│
▼
Save the Changes
│
▼
Close the File
Every Python program that works with files generally follows these four steps.
Opening a File
Before performing any operation, Python must open the file.
Syntax
file = open("filename.txt", "mode")
Here:
• filename.txt → Name of the file
• mode → Specifies what operation we want to perform
Some common file modes are:
Mode
Purpose
"r"
Read the file
"w"
Write into the file (creates a new file or overwrites existing data)
"a"
Append data at the end of the file
"x"
Create a new file only if it does not already exist
The write() Function
The write() function is used to write a single string into a file.
Syntax
Easy2Siksha.com
file.write("Text")
Example
file = open("student.txt", "w")
file.write("Rahul\n")
file.write("Age: 20")
file.close()
Output inside the file
Rahul
Age: 20
How does write() work?
1. Open the file.
2. Python places the cursor at the beginning (or end if append mode is used).
3. The given string is written.
4. The file is closed after saving.
Important Features of write()
• Writes only one string at a time.
• If the file is opened in "w" mode, previous data is erased.
• Returns the number of characters written.
• Suitable for writing small amounts of text.
The writelines() Function
The writelines() function is used to write multiple strings together into a file.
Instead of calling write() many times, we can store several strings inside a list and write
them in one statement.
Syntax
file.writelines(list_of_strings)
Example
Easy2Siksha.com
students = [
"Rahul\n",
"Aman\n",
"Priya\n"
]
file = open("student.txt", "w")
file.writelines(students)
file.close()
Output
Rahul
Aman
Priya
Notice that each string contains \n (newline character). The writelines() function does not
automatically insert new lines. If \n is not included, all text will appear on the same line.
Example:
students = ["Rahul", "Aman", "Riya"]
Output:
RahulAmanRiya
Difference between write() and writelines()
write()
writelines()
Writes one string at a time
Writes multiple strings at once
Accepts only a single string
Accepts a list or iterable of strings
Often called multiple times
Usually called only once
Good for small text
Better for writing many lines efficiently
Returns the number of characters
written
Does not return the total number of
characters
Real-Life Example
Imagine a teacher wants to save students' names.
Using write()
Easy2Siksha.com
file.write("Rahul\n")
file.write("Aman\n")
file.write("Riya\n")
The teacher writes each name one by one.
Using writelines()
names = [
"Rahul\n",
"Aman\n",
"Riya\n"
]
file.writelines(names)
Here, the teacher prepares the entire list first and writes everything together in a single
step.
Why is close() Important?
After completing file operations, we should always close the file.
file.close()
Closing the file:
• Saves all changes.
• Frees system resources.
• Prevents data loss.
• Allows other programs to access the file safely.
Summary Diagram
Python File Processing
Open the File
│
▼
┌───────────────────────┐
│ Read Data (r) │
│ Write Data (w) │
│ Append Data (a) │
└───────────────────────┘
│
Easy2Siksha.com
▼
write() → Write one string
writelines() → Write multiple strings
from a list
│
▼
Close the File
Conclusion
File processing in Python enables programs to store data permanently so it can be used
again even after the program ends. The process involves opening, reading or writing, and
closing a file. The write() function is used to write a single string, making it suitable for small
amounts of text, while the writelines() function writes multiple strings from a list, making it
more convenient when saving several lines at once. Understanding these functions is
essential because file handling is widely used in real-world applications such as storing
student records, employee information, reports, and application data.
2. Explain the concept of a Stack data structure. Discuss its main operations and show how
a stack can be implemented using arrays. Illustrate each operation with an example and
analyse its time complexity.
Ans: 2. Explain the Concept of a Stack Data Structure. Discuss its Main Operations and
Show How a Stack Can Be Implemented Using Arrays. Illustrate Each Operation with an
Example and Analyse its Time Complexity.
A Stack is one of the simplest and most useful data structures in computer science. We use
stacks in our daily lives without even realizing it. Imagine a stack of plates in a kitchen.
Whenever you add a new plate, you place it on the top of the stack. Similarly, when you
need a plate, you always remove the topmost plate first. You cannot directly remove a plate
from the middle or bottom.
This is exactly how a Stack works in programming.
A Stack follows the principle called LIFO (Last In, First Out). This means the last element
inserted into the stack is the first one to be removed.
For example:
• Add 10
• Add 20
• Add 30
The stack becomes:
Easy2Siksha.com
Top
┌─────┐
│ 30 │
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
Bottom
If we remove an element, 30 will come out first because it was added last.
Main Operations of Stack
A stack mainly performs five operations.
1. Push Operation
The Push operation is used to insert a new element at the top of the stack.
Example
Initially:
Top
┌─────┐
│ 20 │
├─────┤
│ 10 │
└─────┘
After pushing 30:
Top
┌─────┐
│ 30 │
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
Here, 30 becomes the new top element.
2. Pop Operation
Easy2Siksha.com
The Pop operation removes the topmost element from the stack.
Example
Before Pop:
Top
┌─────┐
│ 30 │
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
After Pop:
Top
┌─────┐
│ 20 │
├─────┤
│ 10 │
└─────┘
The removed element is 30.
3. Peek (Top)
The Peek operation shows the top element without removing it.
Example:
Top
┌─────┐
│ 20 │ ← Peek returns 20
├─────┤
│ 10 │
└─────┘
The stack remains unchanged.
4. IsEmpty()
This operation checks whether the stack contains any element.
Easy2Siksha.com
If the stack is:
Empty Stack
Top = -1
Then IsEmpty() = True.
Otherwise,
IsEmpty() = False
5. IsFull()
When a stack is implemented using an array, its size is fixed.
Suppose the array size is 5.
Index
0 → 10
1 → 20
2 → 30
3 → 40
4 → 50
Now every position is occupied.
So,
IsFull() = True
No new element can be inserted until one is removed.
Stack Implementation Using Arrays
A stack can easily be implemented using an array.
Suppose the array size is 5.
Initially,
Stack = [ ]
Top = -1
Easy2Siksha.com
Step 1: Push(10)
Stack
Index Value
0 → 10
Top = 0
Step 2: Push(20)
0 → 10
1 → 20
Top = 1
Step 3: Push(30)
0 → 10
1 → 20
2 → 30
Top = 2
Step 4: Pop()
30 is removed.
0 → 10
1 → 20
Top = 1
Notice that we only move the Top pointer. This makes stack operations very fast.
Overflow and Underflow
Two common problems may occur while using a stack.
Stack Overflow
When we try to insert an element into a full stack, it is called Stack Overflow.
Example:
Easy2Siksha.com
Array size = 3
10
20
30
Trying to push 40 will produce Overflow.
Stack Underflow
When we try to remove an element from an empty stack, it is called Stack Underflow.
Example:
Stack = Empty
Calling Pop() will produce Underflow.
Time Complexity of Stack Operations
Operation
Time Complexity
Reason
Push
O(1)
Inserts element at the top only.
Pop
O(1)
Removes only the top element.
Peek
O(1)
Reads the top element without removing it.
IsEmpty
O(1)
Checks the value of the top pointer.
IsFull
O(1)
Compares the top pointer with the maximum array size.
Since every operation works only on the top of the stack, no searching or shifting of
elements is required. Therefore, all basic stack operations take constant time O(1).
Applications of Stack
Stacks are widely used in many real-life and programming situations, such as:
• Managing the Undo feature in text editors.
• Handling the Back button in web browsers.
• Checking balanced parentheses in expressions.
• Function calls and recursion in programming.
• Converting and evaluating arithmetic expressions.
Easy2Siksha.com
Conclusion
A Stack is a simple yet powerful linear data structure that follows the LIFO (Last In, First
Out) principle. Elements are always inserted (Push) and removed (Pop) from the top only.
When implemented using an array, a stack uses a Top pointer to keep track of the latest
element. Operations like Push, Pop, Peek, IsEmpty, and IsFull are very efficient because
they require only O(1) time. Due to its simplicity and speed, the stack is one of the most
commonly used data structures in computer programming and plays an important role in
applications such as undo operations, browser history, expression evaluation, and function
calls.
SECTION-B
3. What is linked list? How is it represented in the memory? Write an algorithm to insert a new
node at a given location in the linked list. Explain this process with the help of an example.
Ans: A Linked List is one of the most important data structures in computer science. At first,
it may sound difficult, but once you understand it with a real-life example, it becomes very
easy.
Imagine you and your friends are standing in a line. Instead of everyone standing shoulder
to shoulder, each person is holding a paper that contains the name of the next person in
the line. If you want to reach the last person, you simply follow the names one by one.
A linked list works in exactly the same way.
What is a Linked List?
A Linked List is a collection of nodes, where each node contains:
1. Data – the actual information stored.
2. Pointer (Link) – the address of the next node.
Unlike an array, the nodes of a linked list are not stored next to each other in memory.
They can be stored anywhere in the computer's memory, but each node knows where the
next node is located.
Think of it like a treasure hunt. Every clue tells you where to find the next clue until you
reach the final destination.
Structure of a Node
Easy2Siksha.com
Every node has two parts.
+-----------+-------------+
| Data | Next Address|
+-----------+-------------+
Example:
Data = 15
Next = Address of next node
Representation of Linked List in Memory
Suppose we want to store three numbers:
10, 20, 30
The computer may store them at completely different memory locations.
Memory Address
1000
+------+-------+
| 10 | 2050 |
+------+-------+
2050
+------+-------+
| 20 | 3500 |
+------+-------+
3500
+------+-------+
| 30 | NULL |
+------+-------+
Here,
• First node is stored at address 1000
• Second node is stored at 2050
• Third node is stored at 3500
Although they are stored at different places, they are connected using their Next Address.
The pointer called HEAD stores the address of the first node.
Easy2Siksha.com
HEAD
|
V
+------+-------+ +------+-------+ +------+------+
| 10 | •--------->| 20 | •--------->| 30 | NULL |
+------+-------+ +------+-------+ +------+------+
NULL means there is no node after the last node.
Why Do We Use a Linked List?
Linked lists are useful because:
• Memory is used efficiently.
• Nodes can be added or deleted easily.
• No need to move other elements while inserting.
• Size can grow or shrink during program execution.
Inserting a New Node at a Given Location
Suppose we already have this linked list:
10 → 20 → 30 → NULL
Now we want to insert 25 after 20.
Step 1: Original List
HEAD
10 → 20 → 30 → NULL
Step 2: Create New Node
+------+------+
| 25 | NULL |
+------+------+
Step 3: Connect the New Node
First, make the new node point to 30.
Easy2Siksha.com
25 → 30
Step 4: Change Previous Node
Now make 20 point to 25.
10 → 20 → 25 → 30 → NULL
The insertion is complete.
Diagram of Insertion
Before Insertion
HEAD
+----+----+ +----+----+ +----+------+
|10 | •------->|20 | •------->|30 | NULL |
+----+----+ +----+----+ +----+------+
New Node
+----+------+
|25 | NULL |
+----+------+
After Insertion
HEAD
+----+----+ +----+----+ +----+----+ +----+------+
|10 | •------->|20 | •------->|25 | •------->|30 | NULL |
+----+----+ +----+----+ +----+----+ +----+------+
Algorithm to Insert a New Node at a Given Position
Algorithm:
1. Start.
2. Create a new node.
3. Store the required data in the new node.
4. If the linked list is empty, make the new node the HEAD and stop.
Easy2Siksha.com
5. Move from the HEAD node until reaching the node just before the desired position.
6. Set the new node's Next pointer to the current node's next node.
7. Change the current node's Next pointer to the new node.
8. Stop.
Example
Suppose the linked list is:
5 → 10 → 20 → 40 → NULL
Insert 30 after 20.
Before
5 → 10 → 20 → 40 → NULL
Create New Node
30
Link New Node
30 → 40
Update Previous Node
20 → 30
Final Linked List
5 → 10 → 20 → 30 → 40 → NULL
Advantages of Linked List
• Dynamic size (can increase or decrease easily).
• Easy insertion and deletion of nodes.
• Efficient memory utilization.
• No shifting of elements is required.
Disadvantages of Linked List
• Extra memory is needed to store pointers.
Easy2Siksha.com
• Sequential access only (cannot directly access any element by index).
• Searching is slower than arrays because each node must be visited one by one.
Conclusion
A Linked List is a dynamic data structure made up of connected nodes, where each node
stores data and the address of the next node. The nodes are stored at different memory
locations, and they are connected through pointers, making the list flexible and easy to
modify. To insert a new node at a given location, we create the new node, connect it to the
following node, and then update the previous node's pointer to the new node. This process
is efficient because no existing data needs to be shifted, making linked lists very useful for
applications where frequent insertion and deletion of data are required.
4. Explain how a priority queue works. Describe the insertion and deletion operations with
the help of an example. How is a priority queue different from a normal queue and where
can it be applied effectively?
Ans: Imagine you are standing in a line at a hospital. Many patients are waiting for the
doctor. Normally, the person who comes first gets treated first. But suddenly, a patient with
a serious heart attack arrives. Even though this patient came later, the doctor treats them
first because their condition is more important.
This is exactly how a Priority Queue works.
A Priority Queue is a special type of queue in which every element is given a priority
(importance). The element with the highest priority is removed first, regardless of when it
was inserted. If two elements have the same priority, they are served according to the order
in which they arrived (First In, First Out).
What is a Priority Queue?
A Priority Queue is a data structure where each item has two things:
1. Data (Value)
2. Priority Number
The element with the highest priority is processed before the others.
For example:
Easy2Siksha.com
Person
Priority
Aman
2
Rahul
5
Simran
3
Here, Rahul will be served first because he has the highest priority (5).
Diagram of a Priority Queue
Insertion Order
Aman (2) → Rahul (5) → Simran (3)
After Arranging by Priority
Front
↓
Rahul (5) → Simran (3) → Aman (2)
The front always contains the element with the highest priority.
Insertion Operation
Insertion means adding a new element to the priority queue.
Example
Initially:
Front
Rahul (5) → Simran (3)
Now insert:
Aman (4)
The queue becomes:
Front
Rahul (5) → Aman (4) → Simran (3)
Easy2Siksha.com
Although Aman was inserted last, he is placed before Simran because his priority is higher.
Steps of Insertion
1. Create a new element.
2. Assign a priority.
3. Compare it with existing elements.
4. Place it at the correct position according to priority.
Deletion Operation
Deletion means removing the element with the highest priority.
Example
Current Queue
Front
Rahul (5) → Aman (4) → Simran (3)
Delete operation:
Rahul (5) is removed.
Remaining Queue
Front
Aman (4) → Simran (3)
Again, the highest priority element is removed first.
Steps of Deletion
1. Look at the front element.
2. Remove the highest-priority element.
3. Shift the remaining elements forward (if needed).
4. The next highest-priority element becomes the new front.
Example with Numbers
Insert the following elements:
Easy2Siksha.com
(10, Priority 2)
(20, Priority 5)
(30, Priority 1)
(40, Priority 4)
After arranging:
Front
20(P5) → 40(P4) → 10(P2) → 30(P1)
Delete once:
20(P5) removed
Remaining Queue
40(P4) → 10(P2) → 30(P1)
Difference Between Normal Queue and Priority Queue
Normal Queue
Priority Queue
Works on FIFO (First In, First Out)
principle.
Works according to priority.
The first inserted element is removed
first.
The highest-priority element is removed first.
Every element has equal importance.
Every element has a different priority level.
Simpler to implement.
Slightly more complex because priorities must be
managed.
Used where order of arrival matters.
Used where importance matters more than arrival
time.
Example
Normal Queue
Front
A → B → C
Delete
A removed
Priority Queue
Easy2Siksha.com
Priorities
A(2)
B(5)
C(3)
Front
B → C → A
Delete
B removed
Even though A entered first, B is removed first because it has the highest priority.
Applications of Priority Queue
Priority queues are very useful in real-life situations where some tasks are more important
than others.
1. Hospital Emergency System
Patients with serious conditions are treated before patients with minor illnesses.
2. CPU Scheduling
The operating system gives the processor to high-priority programs before low-priority
ones.
3. Printer Management
Urgent print jobs are printed before normal documents.
4. Air Traffic Control
Aircraft with emergencies are allowed to land before others.
5. Network Routing
Important data packets are transmitted before less important ones.
6. Event Scheduling
High-priority tasks in applications or software are executed first.
Easy2Siksha.com
Conclusion
A Priority Queue is an advanced version of a normal queue. Instead of serving elements
simply in the order they arrive, it always serves the element with the highest priority first.
The two main operations are Insertion, where a new element is placed according to its
priority, and Deletion, where the highest-priority element is removed first. Because of this
behavior, priority queues are widely used in operating systems, hospitals, printers,
network routing, air traffic control, and many other real-world applications where urgent
or important tasks must be handled before less important ones. They make systems more
efficient by ensuring that critical tasks receive immediate attention.
SECTION-C
5. What do you mean by Binary Tree? How is it implemented in the memory? Explain
different ways to traverse a binary tree using suitable example.
Ans: What is a Binary Tree? How is it Implemented in Memory? Explain Different Ways to
Traverse a Binary Tree with a Suitable Example.
A Binary Tree is one of the most important data structures in computer science. Although
the name sounds difficult, the idea behind it is very simple.
Imagine a family tree. At the top, there is one person (the parent), and below that person
are their children. Similarly, in a binary tree, data is arranged in the form of a tree.
The word "Binary" means two. Therefore, in a binary tree, every node can have a
maximum of two children only:
• Left Child
• Right Child
A node is simply a box that stores some data and links to its children.
Basic Structure of a Binary Tree
Consider the following binary tree:
A
/ \
B C
/ \ \
D E F
Easy2Siksha.com
Here:
• A is called the Root Node because it is the topmost node.
• B and C are children of A.
• D and E are children of B.
• F is the right child of C.
• D, E, and F are called Leaf Nodes because they have no children.
Why Do We Use a Binary Tree?
Binary trees are used because they make storing and searching data much easier.
Some real-life applications include:
• File and folder management
• Search engines
• Database indexing
• Expression evaluation in calculators
• Decision-making systems
• Artificial Intelligence
Instead of searching data one by one, binary trees help organize data efficiently.
How is a Binary Tree Implemented in Memory?
A binary tree is usually implemented using linked representation (nodes and pointers).
Each node contains three parts:
-------------------------
| Left | Data | Right |
-------------------------
• Left Pointer → Stores the address of the left child.
• Data → Stores the actual value.
• Right Pointer → Stores the address of the right child.
For example:
A
/ \
B C
Memory representation:
Easy2Siksha.com
Node A
-------------------------
| B | A | C |
-------------------------
Node B
-------------------------
| NULL | B | NULL |
-------------------------
Node C
-------------------------
| NULL | C | NULL |
-------------------------
Here:
• The left pointer of A stores the address of B.
• The right pointer of A stores the address of C.
• Since B and C have no children, their pointers contain NULL.
This method saves memory because nodes are created only when needed.
What is Tree Traversal?
Traversal means visiting every node of the tree exactly once in a particular order.
Think of it like visiting every room in a house. You can choose different paths to cover all
rooms. Similarly, a binary tree can be traversed in different ways.
There are three main traversal methods:
1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal
Let us understand each one using the same example.
A
/ \
B C
/ \ \
D E F
Easy2Siksha.com
1. Preorder Traversal (Root → Left → Right)
In this method:
• Visit the Root first.
• Then visit the Left Subtree.
• Finally visit the Right Subtree.
Rule:
Root → Left → Right
Step-by-step:
1. Visit A
2. Go to B
3. Visit D
4. Visit E
5. Go to C
6. Visit F
Output:
A B D E C F
2. Inorder Traversal (Left → Root → Right)
Here:
• Visit the Left Subtree first.
• Then visit the Root.
• Finally visit the Right Subtree.
Rule:
Left → Root → Right
Step-by-step:
1. Visit D
2. Visit B
3. Visit E
4. Visit A
5. Visit C
6. Visit F
Output:
Easy2Siksha.com
D B E A C F
This traversal is especially useful in a Binary Search Tree (BST) because it visits the elements
in sorted order.
3. Postorder Traversal (Left → Right → Root)
In this method:
• Visit the Left Subtree.
• Then visit the Right Subtree.
• Visit the Root at the end.
Rule:
Left → Right → Root
Step-by-step:
1. Visit D
2. Visit E
3. Visit B
4. Visit F
5. Visit C
6. Visit A
Output:
D E B F C A
This traversal is commonly used when deleting or freeing an entire tree because child nodes
are processed before their parent.
Summary of Traversal Methods
Traversal Method
Visiting Order
Output
Preorder
Root → Left → Right
A B D E C F
Inorder
Left → Root → Right
D B E A C F
Postorder
Left → Right → Root
D E B F C A
Conclusion
Easy2Siksha.com
A Binary Tree is a hierarchical data structure in which each node can have at most two
children, called the left child and the right child. It organizes data efficiently, making
searching, inserting, and deleting information easier than in many linear structures. In
memory, a binary tree is implemented using nodes, where each node contains data, a left
pointer, and a right pointer that store the addresses of its child nodes. To access every node
in a binary tree, different traversal techniques are used. The three main traversal methods
are Preorder (Root → Left → Right), Inorder (Left → Root → Right), and Postorder (Left →
Right → Root). Each traversal follows a unique visiting order and is useful for different
applications, such as expression evaluation, sorted data retrieval, and deleting tree
structures. Understanding binary trees and their traversal methods forms the foundation for
learning advanced data structures and algorithms.
6. What is Graph? How is it represented in the memory? Explain Breadth-First Search
method to traverse a node of a Graph using suitable example.
Ans: A Graph is a non-linear data structure that is used to represent relationships between
different objects. In simple words, think of a graph as a map of connected points. These
points are called vertices (or nodes), and the lines connecting them are called edges.
For example, imagine you and your friends are connected on a social media platform. Every
person is a node, and every friendship is an edge connecting two people. This forms a
graph. Similarly, Google Maps, Facebook, computer networks, and airline routes all use
graphs.
Basic Components of a Graph
There are two main parts of a graph:
1. Vertex (Node): Represents an object or point.
2. Edge: Represents the connection between two vertices.
For example, consider the following graph:
A
/ \
B C
/ \ \
D E F
Here:
• Vertices = A, B, C, D, E, F
• Edges = A-B, A-C, B-D, B-E, C-F
Easy2Siksha.com
Representation of Graph in Memory
A computer cannot understand diagrams directly, so graphs must be stored in memory.
There are two common methods of representation.
1. Adjacency Matrix
In this method, a 2-dimensional array (matrix) is used.
If two vertices are connected, we write 1; otherwise, we write 0.
For the above graph:
A
B
C
D
E
F
A
0
1
1
0
0
0
B
1
0
0
1
1
0
C
1
0
0
0
0
1
D
0
1
0
0
0
0
E
0
1
0
0
0
0
F
0
0
1
0
0
0
Advantages
• Easy to check whether two vertices are connected.
• Simple to understand.
Disadvantages
• Uses more memory when the graph has fewer edges.
2. Adjacency List
In this method, every vertex stores a list of its neighboring vertices.
A → B → C
B → A → D → E
C → A → F
D → B
E → B
F → C
Advantages
• Saves memory.
• Best for large graphs with fewer connections.
Easy2Siksha.com
Disadvantages
• Slightly slower when checking whether two nodes are directly connected.
What is Breadth-First Search (BFS)?
Breadth-First Search (BFS) is a graph traversal algorithm that visits nodes level by level.
Imagine throwing a stone into a pond. The water waves spread outward in circles. Similarly,
BFS starts from one node and first visits all its immediate neighbors, then the neighbors of
those neighbors, and so on.
It does not go deep into one path first. Instead, it explores every nearby node before
moving farther.
BFS uses a Queue (FIFO - First In, First Out) data structure.
Steps of BFS
Suppose we start from vertex A.
Step 1
Visit A.
Queue:
A
Visited:
A
Step 2
Remove A from the queue.
Visit its neighbors B and C.
Queue:
B C
Easy2Siksha.com
Visited:
A B C
Step 3
Remove B.
Visit its unvisited neighbors D and E.
Queue:
C D E
Visited:
A B C D E
Step 4
Remove C.
Visit its unvisited neighbor F.
Queue:
D E F
Visited:
A B C D E F
Step 5
Remove D, E, and F one by one.
No new neighbors are found.
Queue becomes empty.
Traversal ends.
BFS Traversal Order
Easy2Siksha.com
A → B → C → D → E → F
Working Diagram
A
/ \
B C
/ \ \
D E F
Traversal:
Level 1 : A
Level 2 : B C
Level 3 : D E F
The graph is explored level by level, which is the key idea behind BFS.
BFS Algorithm
1. Start from the source node.
2. Mark it as visited.
3. Insert it into the queue.
4. Remove the front node from the queue.
5. Visit all its unvisited neighboring nodes.
6. Mark them as visited and insert them into the queue.
7. Repeat until the queue becomes empty.
Applications of BFS
Breadth-First Search is widely used in real-life applications such as:
• Finding the shortest path in an unweighted graph.
• Social networking websites to find mutual friends.
• GPS and map navigation.
• Computer network routing.
• Web crawling by search engines.
• Finding connected components in a graph.
Advantages of BFS
Easy2Siksha.com
• Visits all nodes systematically.
• Finds the shortest path in an unweighted graph.
• Easy to implement using a queue.
• Guarantees that the nearest nodes are visited first.
Disadvantages of BFS
• Requires more memory because it stores many nodes in the queue.
• Can become slow for very large graphs.
Conclusion
A Graph is a data structure used to represent objects and the relationships between them. It
consists of vertices (nodes) and edges (connections). Graphs are commonly stored in
memory using either an Adjacency Matrix or an Adjacency List. To explore a graph, one
popular method is Breadth-First Search (BFS), which visits nodes level by level using a
Queue (FIFO). Starting from one node, BFS first explores all nearby nodes before moving to
the next level, making it highly useful for finding the shortest path and solving many real-
world problems such as map navigation, social networks, and computer networking.
SECTION-D
7. Explain the process of Bubble sort using suitable example. Write an algorithm that
performs Bubble sort. Also determine its complexity.
Ans: Introduction
Bubble Sort is one of the simplest sorting algorithms used in computer science. It is mainly
used to arrange numbers or data in ascending order (smallest to largest) or descending
order (largest to smallest). Although it is not the fastest sorting method, it is very easy to
understand, making it ideal for beginners.
The name "Bubble Sort" comes from the way larger elements gradually "bubble up" to the
end of the list, just like air bubbles rise to the surface of water.
What is Bubble Sort?
Easy2Siksha.com
Bubble Sort works by comparing two adjacent (next to each other) elements. If they are in
the wrong order, they are swapped (interchanged). This process continues throughout the
list.
After one complete pass through the list, the largest element reaches its correct position at
the end.
The same process is repeated again for the remaining unsorted elements until the entire list
becomes sorted.
Real-Life Example
Imagine five students standing in a line according to their heights.
Heights:
170 150 180 160 140
The teacher checks two students at a time.
• If the taller student is standing before the shorter one, they exchange places.
• The teacher keeps moving to the next pair.
• After one complete round, the tallest student automatically reaches the last
position.
The teacher repeats the process until everyone stands in the correct order.
This is exactly how Bubble Sort works.
Example of Bubble Sort
Suppose we want to sort the following numbers in ascending order.
40 20 50 10 30
Pass 1
Compare 40 and 20
40 > 20
Swap
20 40 50 10 30
Easy2Siksha.com
Compare 40 and 50
40 < 50
No Swap
20 40 50 10 30
Compare 50 and 10
50 > 10
Swap
20 40 10 50 30
Compare 50 and 30
50 > 30
Swap
20 40 10 30 50
Now 50 has reached its correct position.
Pass 2
Compare 20 and 40
No Swap
20 40 10 30 50
Compare 40 and 10
Swap
20 10 40 30 50
Compare 40 and 30
Swap
20 10 30 40 50
Now 40 is also in its correct position.
Easy2Siksha.com
Pass 3
Compare 20 and 10
Swap
10 20 30 40 50
Compare 20 and 30
No Swap
The list is almost sorted.
Pass 4
No swaps are needed.
The final sorted list is:
10 20 30 40 50
Diagram of Bubble Sort
Original List
40 20 50 10 30
↓
Pass 1
20 40 10 30 50
↓
Pass 2
20 10 30 40 50
↓
Pass 3
10 20 30 40 50
Easy2Siksha.com
↓
Sorted List
Notice that in every pass, the largest unsorted element moves to the end, just like a bubble
rising to the top.
Bubble Sort Algorithm
Algorithm: Bubble Sort
1. Start.
2. Read the array containing n elements.
3. Repeat from the first element to the second-last unsorted element.
4. Compare two adjacent elements.
5. If the first element is greater than the second element, swap them.
6. Continue comparing the next adjacent pair until the end of the array.
7. Repeat the above process until all passes are completed or no swaps occur.
8. Display the sorted array.
9. Stop.
Pseudocode
BubbleSort(A, n)
for i = 0 to n-2
for j = 0 to n-2-i
if A[j] > A[j+1]
swap(A[j], A[j+1])
return A
Complexity of Bubble Sort
The complexity of an algorithm tells us how much time and memory it needs as the input
size increases.
1. Best Case – O(n)
• The array is already sorted.
• Only one pass is needed (with an optimized Bubble Sort that stops if no swaps
occur).
• Therefore, the time complexity is O(n).
Easy2Siksha.com
Example:
10 20 30 40 50
No swapping is required.
2. Average Case – O(n²)
• The numbers are in random order.
• Many comparisons and several swaps are needed.
• The average time complexity is O(n²).
3. Worst Case – O(n²)
• The array is sorted in the reverse order.
• Every comparison results in a swap.
• The maximum number of passes and swaps are required.
• Hence, the worst-case time complexity is O(n²).
Example:
50 40 30 20 10
Every element must move to its correct position through repeated swaps.
Space Complexity – O(1)
Bubble Sort uses only a temporary variable for swapping two elements. It does not require
any extra array or additional memory, so its space complexity is O(1) (constant space).
Advantages of Bubble Sort
• Very easy to understand and implement.
• Suitable for beginners learning sorting algorithms.
• Does not require extra memory (in-place sorting).
• Can finish quickly if the list is already sorted (optimized version).
Disadvantages of Bubble Sort
Easy2Siksha.com
• Slow for large datasets.
• Performs many unnecessary comparisons.
• Much less efficient than algorithms like Merge Sort or Quick Sort.
• Not recommended for applications where high performance is required.
Conclusion
Bubble Sort is a simple and beginner-friendly sorting algorithm that repeatedly compares
and swaps adjacent elements until the list is arranged in the correct order. In each pass, the
largest unsorted element moves to the end of the list, giving the algorithm its name because
it behaves like a bubble rising to the surface. While Bubble Sort is easy to learn and uses
very little extra memory (O(1)), its average and worst-case time complexity is O(n²), making
it inefficient for sorting large amounts of data. Despite this limitation, Bubble Sort remains
an excellent algorithm for understanding the basic principles of sorting and comparison-
based algorithms.
8. Explain in detail the various file organization techniques used in data structures. Discuss
the advantages, disadvantages, and applications of each technique such as sequential,
direct, and indexed file organization. Illustrate your answer with suitable examples.
Ans: When a computer stores a large amount of data, it needs a proper method to arrange
that data inside a file. This method is called File Organization.
In simple words, File Organization is the technique of arranging records in a file so that
they can be stored, searched, updated, and retrieved efficiently.
Think of a library. If books are placed randomly, finding one book becomes very difficult. But
if books are arranged by subject or book number, they can be found quickly. File
organization works in the same way.
There are three major file organization techniques:
1. Sequential File Organization
2. Direct (Random) File Organization
3. Indexed File Organization
1. Sequential File Organization
In Sequential File Organization, records are stored one after another in a particular order.
Usually, they are arranged according to a key field like Student ID or Employee ID.
Example
Easy2Siksha.com
Suppose a school stores student records.
Student ID Name
101 Aman
102 Riya
103 Rahul
104 Simran
105 Karan
The records are stored exactly in this order.
Diagram
Start
|
V
+---------+
| ID 101 |
+---------+
|
V
+---------+
| ID 102 |
+---------+
|
V
+---------+
| ID 103 |
+---------+
|
V
+---------+
| ID 104 |
+---------+
|
V
+---------+
| ID 105 |
+---------+
If we want to find Student ID 105, the computer checks:
101 → 102 → 103 → 104 → 105
This means it searches one record after another.
Advantages
Easy2Siksha.com
• Very easy to understand and implement.
• Suitable for processing large numbers of records.
• Efficient when every record must be read.
• Requires less storage overhead.
Disadvantages
• Searching for a specific record takes more time.
• Inserting a new record in the middle is difficult.
• Deleting records may require rearranging the file.
Applications
• Payroll systems
• Attendance records
• Examination result processing
• Bank statement generation
2. Direct (Random) File Organization
In Direct File Organization, records are stored at a location calculated by a Hash Function.
Instead of searching every record one by one, the computer directly jumps to the required
location.
Think of it like calling a friend using their phone number. You don't search every person in
your contacts—you directly open the correct contact.
Example
Suppose the Hash Function is:
Location = Student ID % 10
Student ID = 123
123 % 10 = 3
The record is stored directly at Location 3.
Diagram
Memory Locations
0
1
Easy2Siksha.com
2
3 ---> Student 123
4
5
6
7
8
9
The computer directly goes to Location 3 without checking other locations.
Advantages
• Very fast searching.
• Quick insertion and deletion.
• Saves search time.
• Best for real-time applications.
Disadvantages
• Hash collisions may occur (two records may get the same location).
• Designing a good hash function is difficult.
• Wasted storage space may occur.
Applications
• Banking systems
• Railway reservation systems
• ATM machines
• Online registration systems
3. Indexed File Organization
In Indexed File Organization, an extra file called an Index is created.
The index contains the key value and the address of the actual record.
Just like a book has an Index showing the page number of each chapter, a computer first
checks the index and then directly reaches the required record.
Example
Index File
Student ID Address
Easy2Siksha.com
101 A1
102 A2
103 A3
104 A4
105 A5
Actual Data File
A1 → Aman
A2 → Priya
A3 → Rahul
A4 → Simran
A5 → Karan
To find Student ID 104:
• Search the index.
• Get Address = A4.
• Directly access record A4.
Diagram
INDEX
ID 101 ---> A1
ID 102 ---> A2
ID 103 ---> A3
ID 104 ---> A4
ID 105 ---> A5
|
V
DATA FILE
A1 --> Aman
A2 --> Riya
A3 --> Rahul
A4 --> Simran
A5 --> Karan
The index acts like a shortcut.
Advantages
• Faster searching than sequential files.
• Suitable for very large databases.
• Easy to update records.
• Multiple indexes can be created.
Easy2Siksha.com
Disadvantages
• Extra storage is needed for the index.
• Updating the index increases processing time.
• Slightly more complex to implement.
Applications
• Library management systems
• Hospital management systems
• University databases
• Banking databases
Comparison of File Organization Techniques
Feature
Sequential
Direct
Indexed
Storage Method
One after another
Hash function
Index + Data file
Search Speed
Slow
Very Fast
Fast
Insertion
Difficult
Easy
Easy
Deletion
Difficult
Easy
Easy
Extra Storage
No
No
Yes (Index)
Best Used For
Reports, payroll
Real-time systems
Large databases
Conclusion
File organization plays an important role in storing and managing data efficiently.
• Sequential File Organization stores records one after another. It is simple but slow
for searching individual records.
• Direct File Organization uses a hash function to access records instantly, making it
the fastest option for quick lookups.
• Indexed File Organization uses an additional index to locate records quickly.
Although it requires extra storage, it provides an excellent balance between speed
and organization.
Choosing the right file organization technique depends on the application's needs.
Sequential organization is best for batch processing, direct organization is ideal for fast real-
time access, and indexed organization is most suitable for large databases where quick
searching and frequent updates are required.
“This paper has been carefully prepared for educational purposes. If you notice any mistakes or
have suggestions, feel free to share your feedback.”
